package digui;

import java.util.ArrayList;
import java.util.List;

public class SubSet {

    public static void main(String[] args) {
        String str = "abc";
        List<String> subsets = generateSubsets(str);
        System.out.println(subsets);
        printAllSubsets(str);
    }
public static void printAllSubsets(String str){
        char[] chs = str.toCharArray();
        subString(chs,0);
}

    public static void subString(char[] str, int i ){
        if(i == str.length ){
            System.out.println(String.valueOf(str));
            return;
        }
        subString(str, i + 1);
        char temp = str[i];
        str[i] = 0;
        subString(str, i + 1);
        str[i] = temp;
    }

    public static List<String> generateSubsets(String str) {
        char[] chs = str.toCharArray();
        List<String> result = new ArrayList<>();
        backtrack(chs, 0, new StringBuilder(), result);
        return result;
    }

    public static void backtrack(char[] str, int index, StringBuilder current, List<String> result){
        if(index == str.length){
            result.add(current.toString());
            return;
        }
        //不包含当前字符
        backtrack(str,index + 1, current, result);
        //包含当前字符
        current.append(str[index]);
        backtrack(str,index + 1, current, result);
        current.deleteCharAt(current.length() - 1);
    }
}
